home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 February: Technology Seed / Mac Tech Seed Feb '97.toast / OpenDoc 1.2b2c1 / Implementation / Storage / Bento / CM / FreeSpce.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-13  |  41.1 KB  |  924 lines  |  [TEXT/MPS ]

  1. /*
  2.     File:        FreeSpce.c 
  3.  
  4.     Contains:    Container Manager Free Space Value Management Routines
  5.  
  6.     Written by:    Ira L. Ruben
  7.  
  8.     Owned by:    Ed Lai
  9.  
  10.     Copyright:    © 1992 - 1996 by Apple Computer, Inc., all rights reserved.
  11.  
  12.     Change History (most recent first):
  13.  
  14.          <2>     1/15/96    TJ        Cleaned Up
  15.          <6>     9/26/95    EL        1286040: Make sure space from global names
  16.                                     do not go to free space if it is not on
  17.                                     disk.
  18.          <5>     8/16/95    EL        1238951: Bento file has wrong deleted-space
  19.                                                     value.
  20.          <4>     12/9/94    EL        #1182275 Optionally do not maintain
  21.                                                     continue flag. Keep all free space, no
  22.                                                     matter how small and delete small segment
  23.                                                     only on closing.
  24.          <3>     9/30/94    EL        #1182275 rename mergeCandidate to
  25.                                                     updateMergeCandidate.
  26.          <2>     8/26/94    EL        #1182275 Handling of temporary free list.
  27.                                                     Correct value in spaceDeletedValue in
  28.                                                     merging. Avoid giving out highly fragmented
  29.                                                     blocks.
  30.          <4>     5/10/94    EL        #1162327. ValueDoNotFree is no longer
  31.                                                     needed.
  32.          <3>      4/6/94    EL        Do not free free space property when it is
  33.                                                     taken over. #1150214
  34.          <2>     3/31/94    EL        Check to see if new free space is just
  35.                                                     behind another free segment. #1150214
  36.          <1>      2/3/94    EL        first checked in
  37.          <5>     1/19/94    EL        Free space just released will not be used
  38.                                                     immediately, but will be keep in a
  39.                                                     temporary list that is merge to the
  40.                                                     permanent free list at close time.
  41.          <4>      1/6/94    EL        Add cmTakeOverFreeList call to transfer the
  42.                                                     free list.
  43.          <3>    11/16/93    EL        Correct the value of spaceDeletedValue.
  44.          <2>     11/4/93    EL        Do not put deleted space in target
  45.                                                     container into the free list. Arrange data
  46.                                                     in free list in ascending order so that it
  47.                                                     can be merged into larger blocks.
  48.  
  49.     To Do:
  50. */
  51.  
  52. /*---------------------------------------------------------------------------*
  53.  |                                                                           |
  54.  |                            <<< FreeSpce.c  >>>                            |
  55.  |                                                                           |
  56.  |          Container Manager Free Space Value Management Routines           |
  57.  |                                                                           |
  58.  |                               Ira L. Ruben                                |
  59.  |                                 4/23/92                                   |
  60.  |                                                                           |
  61.  |                    Copyright Apple Computer, Inc. 1992-1994               |
  62.  |                           All rights reserved.                            |
  63.  |                                                                           |
  64.  *---------------------------------------------------------------------------*
  65.  
  66.  This file contains routines for reusing deleted data space.  The routines record the
  67.  deleted space and reuse it for value data writes.
  68.  
  69.  The free space is maintained as a list of value segment entries for a "free space"
  70.  property belonging to the TOC ID 1 entry.  It is written to the container like other ID 1
  71.  properties to keep track of all the deleted space.
  72.  
  73.  If a container is opened for reusing free space, we use the free list to reuse the space.
  74. */
  75.  
  76.  
  77. #include <stddef.h>
  78. #include <stdio.h>
  79.  
  80. #ifndef __CMTYPES__
  81. #include "CMTypes.h"
  82. #endif
  83. #ifndef __CM_API__
  84. #include "CMAPI.h"
  85. #endif
  86. #ifndef __LISTMGR__
  87. #include "ListMgr.h"
  88. #endif
  89. #ifndef __TOCENTRIES__
  90. #include "TOCEnts.h"   
  91. #endif
  92. #ifndef __TOCOBJECTS__
  93. #include "TOCObjs.h"   
  94. #endif
  95. #ifndef __TOCIO__
  96. #include "TOCIO.h"
  97. #endif
  98. #ifndef __GLOBALNAMES__
  99. #include "GlbNames.h"   
  100. #endif
  101. #ifndef __CONTAINEROPS__
  102. #include "Containr.h"  
  103. #endif
  104. #ifndef __HANDLERS__
  105. #include "Handlers.h"
  106. #endif
  107. #ifndef __SESSIONDATA__
  108. #include "Session.h"          
  109. #endif
  110. #ifndef __FREESPACE__
  111. #include "FreeSpce.h" 
  112. #endif
  113.                                                                     
  114.                                                                     
  115.                                                                     CM_CFUNCTIONS
  116.  
  117. /* The following generates a segment directive for Mac only due to 32K Jump Table             */
  118. /* Limitations.  If you don't know what I'm talking about don't worry about it.  The        */
  119. /* default is not to generate the pragma.  Theoritically unknown pragmas in ANSI won't    */
  120. /* choke compilers that don't recognize them.  Besides why would they be looked at if        */
  121. /* it's being conditionally skipped over anyway?  I know, famous last words!                        */
  122.  
  123. #if CM_MPW
  124. #pragma segment TOCEntries
  125. #endif
  126.  
  127. /*----------------------------------------------------------------*
  128.  | removeEmptyFreeSpace - remove free space header if it is empty |
  129.  *----------------------------------------------------------------*
  130.  
  131.  Check to see if free space is empty. If it is, completely remove that property.
  132. */
  133.  
  134. static void CM_NEAR removeEmptyFreeSpace(ContainerPtr container)
  135. {
  136.     TOCObjectPtr     theTOCObject;
  137.     TOCPropertyPtr theFreeListProperty;
  138.     /* If there are no more free list entries, delete the value header and the "free             */
  139.     /* space" property from TOC ID 1...                                                                                                        */
  140.         
  141.     TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
  142.     if (freeSpaceValueHdr) {
  143.         if (cmIsEmptyList(&freeSpaceValueHdr->valueList)) {            /* if no more free list...    */
  144.             theFreeListProperty = freeSpaceValueHdr->theProperty;    /* ...get owning property        */
  145.             theTOCObject                 = theFreeListProperty->theObject;    /* ...get owning object (1)    */
  146.             CMfree(freeSpaceValueHdr);                                                        /* ...clobber the value hdr    */
  147.             CMfree(cmDeleteListCell(&theTOCObject->propertyList, theFreeListProperty));
  148.             container->freeSpaceValueHdr = NULL;                                    /* ...no more free list            */
  149.         }
  150. #if CMKEEP_CONTINUE_FLAG
  151.         else if (cmCountListCells(&freeSpaceValueHdr->valueList) == 1)
  152.             freeSpaceValueHdr->valueFlags &= ~ValueContinued;            /* only 1, then no cont            */
  153. #endif
  154.     }
  155. }
  156.  
  157. /*------------------------------------------------*
  158.  | deleteFreeListEntry - delete a free list entry |
  159.  *------------------------------------------------*
  160.  
  161.  This routine removes the specified free list entry and frees up its space.  If this is 
  162.  the last entry of the free list, the free list property itself (along with its value
  163.  header, of course) are removed.
  164.  
  165.  Note, this routine is a low-level routine called from the other routines in this file.
  166.  As such there are no error checks.  The caller is assumed "happy" with what its doing by
  167.  the time it calls this routine.
  168. */
  169.  
  170. static void CM_NEAR deleteFreeListEntry(TOCValuePtr theValue)
  171. {
  172.     ContainerPtr      container = theValue->theValueHdr->container;
  173.     TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
  174. #if CMKEEP_CONTINUE_FLAG
  175.     TOCValuePtr         prevValue;
  176.     
  177.     prevValue = (TOCValuePtr) cmGetPrevListCell(theValue);
  178.     if (prevValue) {
  179.         prevValue->flags = theValue->flags;                /* if theValue is last, now you are last     */
  180.     }
  181. #endif
  182.  
  183.     /* Delete the value entry from its list and free its space...                                                    */
  184.     
  185.     freeSpaceValueHdr->size -= theValue->value.notImm.valueLen;
  186.     CMfree(cmDeleteListCell(&freeSpaceValueHdr->valueList, theValue));
  187.     
  188.     removeEmptyFreeSpace(container);                        /* remove the property if it is empty            */
  189. }
  190.  
  191. /*----------------------------------------------------------------------------------*
  192.  | rearrangePermFreeList - arrange items in free list in ascending order and merged |
  193.  *----------------------------------------------------------------------------------*
  194.  
  195.     !.0d5 or earlier code writes a free list that is not in sorted order.
  196.  
  197.     This version expects free list item to be in sorted order.
  198.     
  199.     We do this by moving all the items in the perm free list into the temp free list.
  200.     Then we move it back from the temp free list to the perm free list.
  201.     Since the 2nd operation always ensure list items are in ascending order and
  202.     adjacent items would be combined into one. We can back the list we want.
  203.     
  204.     However we do not want to move items originally in the temp free list to the perm
  205.     free list. So we save the temp free list in the beginning and restore the temp free 
  206.     list at the end.
  207. */
  208.  
  209. static void CM_NEAR rearrangePermFreeList(ContainerPtr container)
  210. {
  211.     ListHdr                 saveList = container->tmpList;
  212.     TOCValuePtr             theValue;
  213.     CM_ULONG                size;
  214.     
  215.     cmInitList(&container->tmpList);    
  216.     theValue = (TOCValuePtr)cmGetListHead(&container->freeSpaceValueHdr->valueList);
  217.     
  218.     while (theValue) {                                                            /* scan the free space list...                */
  219.         size = theValue->value.notImm.valueLen;
  220.         container->spaceDeletedValue->value.imm.ulongValue -= size;
  221.         cmAddToTmpFreeList(container, theValue->value.imm.ulongValue, size);
  222.         theValue = (TOCValuePtr)cmGetNextListCell(theValue);
  223.     }    
  224.     container->freeSpaceValueHdr->size = 0;                                        /* we removed everything        */
  225.     cmFreeAllListCells(&container->freeSpaceValueHdr->valueList, SESSION);
  226.     cmCopyTmpFreeToTOC(container);            /* move from temp tmp list back to perm free list    */
  227.     
  228.     container->tmpList = saveList;
  229. }
  230.  
  231. /*------------------------------------------------------------------------*
  232.  | addToPermFreeList - add freed space to the permanent "free space" list |
  233.  *------------------------------------------------------------------------*
  234.  
  235.     This routine takes some free space and put it into the permanent free space property
  236.     for use in future.
  237.  
  238.   As part of the freeing process, we scan the free list to see if the new space can be 
  239.     combined with an already existing entry.  It's a sort of on-the-fly garbage collector.
  240.     
  241.     For new containers, there is no "free space" property initially for ID 1.  It is created
  242.     here the first time we need to free space.  We remember the value header for the "free
  243.     space" property so that we may efficiently get at the list on all future calls.
  244. */
  245.  
  246. static void CM_NEAR addToPermFreeList(ContainerPtr container,
  247.                                               CM_ULONG offset, CM_ULONG size)
  248. {
  249.     TOCObjectPtr      theTOCobject;
  250.     TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
  251.     TOCValuePtr         theValue = NULL, nextValue;
  252.     CM_ULONG              valueStart, valueEndPlus1, prevStart;
  253.     TOCValueBytes  valueBytes;
  254.     void                     *toc;
  255.     
  256.         
  257.     /* See if the space we're freeing can be combined with some already existing free            */
  258.     /* space.  If the new space is already freed (now how could that happen?) we ignore        */
  259.     /* the new space.  If the chunk of space we are about to free is less than the size        */
  260.     /* of a TOC entry, we ignore it (losing track of that space), since it would cost more*/
  261.     /* to remember it.  However, if that space can be combined with already existing             */
  262.     /* space, we do the combining.                                                                                                                */ 
  263.     
  264.     if (freeSpaceValueHdr != NULL) {                                /* if free space list exists...                */
  265.         theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
  266.         prevStart = 0;
  267.         
  268.         while (theValue) {                                                        /* scan the free space list...                */
  269.             valueStart         = theValue->value.imm.ulongValue;
  270.             valueEndPlus1 = valueStart + theValue->value.notImm.valueLen;
  271.             if (prevStart > valueStart) {
  272.                 /* the list is not in order, must have been written by 1.0d5 or earlier software*/
  273.                 rearrangePermFreeList(container);                            /* make sure it is in order first    */
  274.                 addToPermFreeList(container, offset, size);        /* now do it again                                */
  275.                 return;
  276.             }
  277.             prevStart = valueStart;
  278.             if (offset >= valueStart) {                                                     /* this is after this                */
  279.                 if (offset <= valueEndPlus1) {                                             /* have overlap or concat        */
  280.                     if (offset + size > valueEndPlus1) {            /* combine new amount with this entry*/
  281.                         size = (offset + size) - valueEndPlus1;    /* reduce actual size to add in                */
  282.                         theValue->value.notImm.valueLen += size;/* this is what we combine in                    */
  283.                         freeSpaceValueHdr->size += size;                /* echo total size in header                    */
  284.                         container->spaceDeletedValue->value.imm.ulongValue += size;
  285.                         /* we may able to join with the next value to form a single value                        */
  286.                         valueEndPlus1 += size;
  287.                         nextValue = (TOCValuePtr)cmGetNextListCell(theValue);
  288.                         if (nextValue) 
  289.                             if (nextValue->value.imm.ulongValue <= valueEndPlus1) {
  290.                                 /* we can combine with next value, absorb the next value in this one        */
  291.                                 theValue->value.notImm.valueLen = nextValue->value.imm.ulongValue +
  292.                                     nextValue->value.notImm.valueLen - theValue->value.imm.ulongValue;
  293.                                 /* we bump up the free space to cancel out deleteFreeListEntry                    */
  294.                                 freeSpaceValueHdr->size += nextValue->value.imm.ulongValue;
  295.                                 /* now everything in next value in in this one, we can delete next value*/
  296.                                 deleteFreeListEntry(nextValue);
  297.                             }
  298.                     }
  299.                     return;                                                                        /* exit since we updated "old" entry*/
  300.                 }
  301.             } else if (offset + size >= valueStart) {            /* can combine from the lower end        */
  302.                 theValue->value.imm.ulongValue = offset;        /* this is the low end                            */
  303.                 if (offset + size > valueEndPlus1)
  304.                     valueEndPlus1 = offset + size;
  305.                 size = valueEndPlus1 - offset - theValue->value.notImm.valueLen; /* increment */
  306.                 theValue->value.notImm.valueLen += size;/* this is what we combine in                    */
  307.                 freeSpaceValueHdr->size += size;                /* echo total size in header                    */
  308.                 container->spaceDeletedValue->value.imm.ulongValue += size;
  309.                 return;                                                                        /* exit since we updated "old" entry    */
  310.             } else
  311.                 break;                                                                            /* it should be inserted before here*/
  312.             theValue = (TOCValuePtr)cmGetNextListCell(theValue);
  313.         }
  314.     } /* checking for combining */
  315.     
  316. #if 0    
  317.     /* Since the cost of recording the free space in the container will be a TOC entry, we*/
  318.     /* only record free space chucks whose size is LARGER than a TOC entry.  Since we         */
  319.     /* couldn't combine it with already existing space, we simply exit and forget it.            */
  320.  
  321.     #if TOC1_SUPPORT
  322.     if (container->majorVersion == 1) {
  323.         if (size <= TOCentrySize) return;
  324.     } else 
  325.         if (size <= MinTOCSize) return;
  326.     #else
  327.     if (size <= MinTOCSize) return;
  328.     #endif
  329. #endif
  330.     /* If this is the first freed space in the container, create the "free space" property*/
  331.     /* for the TOC object 1.  Otherwise, just use it. We remember the pointer to the value*/
  332.     /* header for this property in the container.  Note, the TOC we want to deal with here*/
  333.     /* is the container's own (private) TOC.  This will be different from the current TOC    */
  334.     /* when we're updating containers.                                                                                                        */
  335.     
  336.     if (freeSpaceValueHdr == NULL) {                                /* if 1st free space for container...    */
  337.         toc = container->toc;                                                    /* ...remember current TOC                        */
  338.         container->toc = container->privateTOC;                /* use container's own (private) TOC    */
  339.         
  340.         theTOCobject = cmDefineObject(container,            /* ...create "free space" property        */
  341.                                                                      CM_StdObjID_TOC, CM_StdObjID_TOC_Free,
  342.                                                                     CM_StdObjID_TOC_Type, NULL,
  343.                                                                      container->generation, 0,
  344.                                                                     (ObjectObject | ProtectedObject),
  345.                                                                      &freeSpaceValueHdr);
  346.         
  347.         container->toc = toc;                                                    /* restore current container                    */
  348.         if (theTOCobject == NULL) return;
  349.         freeSpaceValueHdr->valueFlags |= ValueProtected;/* don't allow writing to this value*/
  350.         container->freeSpaceValueHdr = freeSpaceValueHdr;
  351.     } 
  352.  
  353.     /* At this point we want to create a new free list entry for the newly freed offset     */
  354.     /* size.  The value list are standard value entries for the "free space" property of    */
  355.     /* TOC object ID 1.                                                                                                                                        */
  356.  
  357.     container->spaceDeletedValue->value.imm.ulongValue += size;
  358.  
  359.     (void)cmSetValueBytes(container, &valueBytes, Value_NotImm, offset, size);
  360.     
  361. #if CMKEEP_CONTINUE_FLAG
  362.     if (theValue) {                                                                            /* it should come before this            */
  363.         /* create a new value, and insert before theValue                                                                        */
  364.         /* if we are successful, then update the value header to reflect it                                    */
  365.         if (cmInsertBeforeListCell(&freeSpaceValueHdr->valueList, 
  366.                                                              cmCreateValueSegment(freeSpaceValueHdr, &valueBytes, kCMContinued), 
  367.                                                              theValue)) {
  368.             freeSpaceValueHdr->valueFlags |= ValueContinued;/* also set a more convenient flag    */
  369.             freeSpaceValueHdr->size += size;                                /* echo total size in header                    */
  370.         }
  371.     } else {                                                                                        /* we should put it at very end        */
  372.         theValue = (TOCValuePtr)cmGetListTail(&freeSpaceValueHdr->valueList);
  373.         if (theValue) {
  374.             theValue->flags |= kCMContinued;                                /* flag the current value as cont'd    */
  375.             freeSpaceValueHdr->valueFlags |= ValueContinued;/* also set a more convenient flag    */
  376.         }
  377.         cmAppendValue(freeSpaceValueHdr, &valueBytes, 0);
  378.     }
  379. #else
  380.     if (theValue) {                                                                            /* it should come before this            */
  381.         /* create a new value, and insert before theValue                                                                        */
  382.         /* if we are successful, then update the value header to reflect it                                    */
  383.         if (cmInsertBeforeListCell(&freeSpaceValueHdr->valueList, 
  384.                                                              cmCreateValueSegment(freeSpaceValueHdr, &valueBytes, 0), 
  385.                                                              theValue)) {
  386.             freeSpaceValueHdr->size += size;                                /* echo total size in header                    */
  387.         }
  388.     } else {                                                                                        /* we should put it at very end        */
  389.         theValue = (TOCValuePtr)cmGetListTail(&freeSpaceValueHdr->valueList);
  390.         cmAppendValue(freeSpaceValueHdr, &valueBytes, 0);
  391.     }
  392. #endif
  393. }
  394.  
  395. /*-----------------------------------------------------------------------*
  396.  | cmAddToTmpFreeList - add freed space to the temporary "free space" list |
  397.  *-----------------------------------------------------------------------*
  398.  
  399.     This routine takes some free space and put it into the temporary free space property
  400.     for use in future.
  401.     
  402.     We want to put thing in the temporary free list for two reasons.
  403.     
  404.     For container opened for writing, we don't want to write into the old container
  405.     before we close it in case it crashes before it is closed, so we put it into
  406.     the temporary free list.
  407.     
  408.     For container opened for updating, we have free space that can be reused if
  409.     it is merged. Since we do not know whether we will just close the container
  410.     or merge it, we put it in the temporary free list and put it on the real
  411.     free list only if we do a merge at close time.
  412.  
  413. */
  414.  
  415. void cmAddToTmpFreeList(ContainerPtr container, CM_ULONG offset, CM_ULONG size)
  416. {
  417.   FreeSpaceItem    *toBeFree;
  418.  
  419.     toBeFree = CMmalloc(sizeof(FreeSpaceItem));            /* so we can get rid of SCpp warning*/
  420.     if (toBeFree) {
  421.         toBeFree->offset = offset;
  422.         toBeFree->size = size;
  423.         cmAppendListCell(&container->tmpList, toBeFree);
  424.     }
  425. }
  426.  
  427. /*-----------------------------------------------------------------------------------*
  428.  | cmAddValueToTmpFreeList - add space in a value to the temporary "free space" list |
  429.  *-----------------------------------------------------------------------------------*
  430.  
  431.     This routine put all the free space used by a value into the temporary free list
  432.  
  433. */
  434.  
  435. void cmAddValueToTmpFreeList(TOCValueHdrPtr theValueHdr)
  436. {
  437.     TOCValuePtr theValue = (TOCValuePtr)cmGetListHead(&theValueHdr->valueList);
  438.  
  439.     while (theValue) {
  440.         /* use targetContainer->updatingContainer because during applyUpdate                        */
  441.         /* updatingContainer point to itself, so we need to get the real updating cntr    */
  442.         cmAddToTmpFreeList(theValueHdr->container->targetContainer->updatingContainer,
  443.                                              theValue->value.notImm.value,
  444.                                              theValue->value.notImm.valueLen);
  445.         theValue = (TOCValuePtr)cmGetNextListCell(theValue);
  446.     }
  447. }
  448.  
  449. /*----------------------------------------------------------------------*
  450.  | cmAddToFreeList - add freed space to the permanent "free space" list |
  451.  *----------------------------------------------------------------------*
  452.  
  453.  This routine is called whenever space for value data is to be freed.  The space is
  454.  recorded in a free list. The free list entries are maintained as value segments belonging
  455.  to the "free space" property of TOC object ID 1.
  456.  
  457.  The amount of space to be freed is specified in one of two possible ways:
  458.  
  459.          1. By passing a pointer to a value segment in theValueToFree.  The offset and size
  460.              are extracted from the segment info.  If theValueToFree is for an immediate value,
  461.              we simply exit since there is no container space to actually free.  Global names,
  462.              as usual, are handled specially.  In particular, for no global names that have not
  463.              yet been written to the container yet (we keep 'em in memory unto we write the TOC
  464.              at container close time), then we ingore them just like immediates.  For "old"
  465.              global names we do account for the space.
  466.              
  467.         2. If theValueToFree is passed as NULL, then an explicit size and offset may be
  468.              passed.  Note that a non-null theValueToFree has precedence over explicit offset
  469.              and size.
  470. */
  471.  
  472. void cmAddToFreeList(ContainerPtr container, TOCValuePtr theValueToFree,
  473.                                         CM_ULONG offset, CM_ULONG size)
  474. {
  475.     Boolean        mayGoToTmpList = false;
  476.  
  477.     /* We only track free space when a container is opened for writing or updating.              */
  478.     /* However, even when writing there is an override switch to suppress the space                */
  479.     /* tracking.  This is done during applying updates during open time.  We don't want        */
  480.     /* to track what's going on then!                                                                                                            */
  481.     
  482.     if (!container->trackFreeSpace ||                                /* if no tracking of free space or...    */
  483.           (container->useFlags & kCMWriting) == 0)        /* ...not opened for writing/updating    */
  484.         return;                                                                                /* ...exit                                                        */
  485.     
  486.     /* Get the offset and size from the value if it's specified. This is the amount being    */
  487.     /* freed.  If theValueToFree is NULL, then the offset and size must be explicitly         */
  488.     /* specified, otherwise these parameters are ignored.  As a safety, if the value is        */
  489.     /* passed, but it is for an immediate value, there is no space being given up, so we    */
  490.     /* just exit.                                                                                                                                                    */
  491.     
  492.     if (theValueToFree != NULL) {                                        /* if value explicitly specified...        */
  493.         if ((theValueToFree->container->depth == 1) && (container->useFlags & kCMMerging))
  494.             mayGoToTmpList = true;
  495.         else if (theValueToFree->container != container)/* does it belong to this level?        */
  496.             return;                                                                                /* no, then just return                            */
  497.         if (theValueToFree->flags & kCMGlobalName) {    /* ...handle global names specially        */
  498.             if (theValueToFree->theValueHdr->valueRefCon == 0) 
  499.                 return;                                                                     /* not written, nothing to free                */
  500.             offset = theValueToFree->value.globalName.offset;    
  501.             if (offset == 0) return;                                         /* this is an extra precaution check */
  502.             size = GetGlobalNameLength(theValueToFree->value.globalName.globalNameSymbol) + 1;
  503.         } else if (theValueToFree->flags & kCMImmediate)
  504.             return;                                                                            /* ...ignore immediates...                        */
  505.         else {                                                                                /* ...have "normal" value                            */
  506.             offset = theValueToFree->value.notImm.value;
  507.             size      = theValueToFree->value.notImm.valueLen;
  508.         }
  509.     }
  510.     
  511.     if (size == 0) return;
  512.     
  513.     if (mayGoToTmpList || (container->useFlags & (kCMUpdateByAppend | kCMUpdateTarget) == 0)) {
  514.         /* If the space is from previous container, or in the same container but we are not */
  515.         /* doing an updating, do not reuse freespace until the container is closed.                    */
  516.         /* So even if we crashes before the container is closed, old data is not destroyed    */
  517.         cmAddToTmpFreeList(container, offset, size);
  518.     }
  519.     else {    
  520.         /* for updating, we do not touch the data in old container directly, so any free      */
  521.         /* space comes from the new container and we can put it into the free list directly */
  522.         addToPermFreeList(container, offset, size);
  523.     }
  524. }
  525.  
  526. /*------------------------------------------------------*
  527.  | tmpListCB - add freed space to the "free space" list |
  528.  *------------------------------------------------------*
  529.  
  530.  Action routine to take a free space and add it to the permanent free space list.
  531.  */
  532.  
  533. static void CM_NEAR tmpListCB(void * theCell, CMRefCon refCon)
  534. {
  535.     FreeSpaceItem    *toBeFree = (FreeSpaceItem *)theCell;
  536.  
  537.     addToPermFreeList((ContainerPtr)refCon, toBeFree->offset, toBeFree->size);
  538. }
  539.  
  540. /*---------------------------------------------------------------*
  541.  | cmCopyTmpFreeToTOC - add freed space to the "free space" list |
  542.  *---------------------------------------------------------------*
  543.  
  544.     This routine goes through the list of temporary free space and merge each one into
  545.     the permanent free space. At the end the temporary free space are removed.
  546. */
  547.  
  548. void cmCopyTmpFreeToTOC(ContainerPtr container)
  549. {
  550.     cmForEachListCell(&container->tmpList, (CMRefCon)container, tmpListCB);
  551.  
  552.   cmFreeAllListCells(&container->tmpList, container->sessionData);
  553. }
  554.  
  555. /*-----------------------------------------------------------------------*
  556.  | cmRemoveSmallFreeSpace - remove segment too small to be worth keeping |
  557.  *-----------------------------------------------------------------------*
  558.  
  559.  There is certain overhead of storing a value segment. If a free space segment is so small
  560.  that the overhead of storing it is greater than the free space itself, then it is not
  561.  worth to keep the free space. So we go through the free space list and remove the small
  562.  segments.
  563.  
  564.  On the other hand, later we may free space that are are around these small segments.
  565.  So if we ignore these small segments, we may cause fragmentation of the free space
  566.  later. So we should revisit this issue to see if it is worthwhile to keep them anyway.
  567. */
  568.  
  569. void cmRemoveSmallFreeSpace(ContainerPtr container)
  570. {
  571.     TOCValuePtr         theValue, nextValue;
  572.     
  573.     TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
  574.     if (freeSpaceValueHdr) {
  575.         theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
  576.         while (theValue) {
  577.             nextValue = (TOCValuePtr)cmGetNextListCell(theValue);
  578.             /* If the free space is smaller than overhead of keeping track of it, remove it             */
  579.             if (theValue->value.notImm.valueLen < MinTOCSize) {
  580.                 freeSpaceValueHdr->size -= theValue->value.notImm.valueLen;
  581.                 CMfree(cmDeleteListCell(&freeSpaceValueHdr->valueList, theValue));
  582.             }
  583.             theValue = nextValue;
  584.         } /* while value */
  585.         
  586.         removeEmptyFreeSpace(container);
  587.     }
  588. }
  589.  
  590.  
  591. /*--------------------------------------------------------------*
  592.  | cmGetFreeListEntry - get a free space entry from "free list" |
  593.  *--------------------------------------------------------------*
  594.  
  595.  This routine returns one free list entry (if one exists).  The offset from that entry is
  596.  returned as the function result.  The size is returned in actualSize.  If there is no 
  597.  free space, or we can't find one big enough (see mustAllFit below), 0 is returned as the
  598.  function result and for the actualSize.  0's are also returned if the container was not
  599.  opened to reuse free space.
  600.  
  601.  The desiredSize is passed as what the caller would like as the single free list entry
  602.  amount, i.e., a "best fit".  It is also used when we find a bigger free list entry and
  603.  only have to reduce part of it.
  604.  
  605.  If mustAllFit is true, then we MUST find a single free list segment big enough or 0 will
  606.  be returned.  This is used for data that is not allowed to be continued with multiple
  607.  value segments (e.g., global names).
  608.  
  609.  The free list is built by cmAddToFreeList() as value segments belonging to a value header
  610.  of the "free space" property for TOC object ID 1.   If all the free list entries are
  611.  exhausted, the value header is freed along with the property.  If space is ever given up
  612.  after this through cmAddToFreeList(), it will recreate the "free space" property, its
  613.  value header, and the free list value entry segments.
  614. */
  615.  
  616. CM_ULONG cmGetFreeListEntry(ContainerPtr container, 
  617.                                                         CM_ULONG desiredSize, Boolean mustAllFit,
  618.                                                         CM_ULONG *actualSize)
  619. {
  620.     TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
  621.     TOCValuePtr         theValue;
  622.     CM_ULONG              offset;
  623. #if MinFragmentSize
  624.     CM_ULONG              minSegmentSize;
  625. #endif
  626.  
  627.     /* Return null amount if there is no free list or not updating...                                            */
  628.     
  629.     if (freeSpaceValueHdr == NULL || (container->useFlags & kCMReuseFreeSpace) == 0)
  630.         return (*actualSize = 0);
  631.     
  632.     /* Use the next available free list entry (segment) no matter what it is unless we         */
  633.     /* mustAllFit.  For mustAllFit we must scann the free list for a single entry large        */
  634.     /* enough to hold the entire data (desiredSize bytes).                                                                */
  635.     
  636.     /* Note as just said, when mustAllFit is false, we just use the first free list             */
  637.     /* segment on the list.  A better algorithm might be to use the desired amount and         */
  638.     /* find a "best fit" by scanning the free list just as in the mustAllFit case.  So         */
  639.     /* which is better in time and/or space?  A scan each time or just reusing each entry */
  640.     /* unconditionally.  The latter guarantees reuse of all available space.  But the         */
  641.     /* former potentially uses less value segments.  For now I take the easy way.                    */
  642.     
  643.     /* Note we still need it to split larger free space entries when we don't need all        */
  644.     /* the space from an entry.                                                                                                                        */
  645.     
  646.     theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
  647.     
  648. #if MinFragmentSize
  649.     if ((mustAllFit) || (desiredSize <= MinFragmentSize))
  650.         /* If the block is small, it does not make sense to have different segments. So we    */
  651.         /* treat it as a single segment to avoid fragmentation.                                                            */
  652.         minSegmentSize = desiredSize;
  653.     else {
  654.         /* Even if it is a large block, we still don't want it to fragment too much.                */
  655.         /* This is especially true since the block may be an embedded container. So we try    */
  656.         /* to limit the number of segments                                                                                                    */
  657. #if MaxFragmentCount
  658.         minSegmentSize = desiredSize / MaxFragmentCount;
  659.         if (minSegmentSize < MinFragmentSize)
  660.             minSegmentSize = MinFragmentSize;
  661. #else
  662.         minSegmentSize = MinFragmentSize;
  663. #endif
  664.     }
  665.     
  666.     while (theValue) {                                                                                /* ...scan free list                */
  667.         if (theValue->value.notImm.valueLen >= minSegmentSize)     /* ...for one big enough        */
  668.             break;
  669.         theValue = (TOCValuePtr)cmGetNextListCell(theValue);
  670.     }
  671.     if (theValue == NULL) return (*actualSize = 0);                    /* if none found, too bad        */
  672. #else
  673.     if (mustAllFit) {                                                                                    /* if must find single seg    */
  674.         while (theValue) {                                                                            /* ...scan free list                */
  675.             if (theValue->value.notImm.valueLen >= desiredSize)     /* ...for one big enough        */
  676.                 break;
  677.             theValue = (TOCValuePtr)cmGetNextListCell(theValue);
  678.         }
  679.         if (theValue == NULL) return (*actualSize = 0);                    /* if none found, too bad        */
  680.     }
  681. #endif
  682.     
  683.     offset             = theValue->value.notImm.value;                                /* set to return this offset*/
  684.     *actualSize = theValue->value.notImm.valueLen;                        /* and this size (maybe!)        */
  685.     
  686.     /* If the free list entry is big enough to cover all that is desired, use only the        */
  687.     /* required amount and retain the free list entry.  It must, however, be reduced by        */
  688.     /* the amount used.                                                                                                                                        */
  689.         
  690.     if (desiredSize < *actualSize) {                                                    /* free entry is too big        */
  691.         theValue->value.notImm.value    += desiredSize;                    /* ...cut it down                        */
  692.         theValue->value.notImm.valueLen -= desiredSize;
  693.         container->spaceDeletedValue->value.imm.ulongValue -= desiredSize; /* cut total            */
  694.         freeSpaceValueHdr->size -= desiredSize;                                 /* less free space now            */
  695.         *actualSize = desiredSize;                                                            /* return what was desired    */
  696.         return (offset);
  697.     }
  698.     
  699.     /* Now that we used an entire an free list entry, delete it from the free list and         */
  700.     /* free its memory.  If there are no more free list entries, delete the value header     */
  701.     /* and the "free space" property from TOC ID 1...                                                                            */
  702.     
  703.     deleteFreeListEntry(theValue);
  704.     
  705.     container->spaceDeletedValue->value.imm.ulongValue -= *actualSize; /* cut total                */
  706.     
  707.     return (offset);                                                                                    /* return new space to use    */
  708. }
  709.  
  710. /*--------------------------------------------------------------------------*
  711.  | cmTakeOverFreeList - have one container take the free space from another |
  712.  *--------------------------------------------------------------------------*
  713.  
  714.  When a target container is open by a container, we want to take over the
  715.  free space in the target container so that we can reuse the free space
  716.  in the target container. Since the target container is open read only, we
  717.  cannot update the free space list there. So the update container move the list
  718.  over so that it becomes the free list of the update container.
  719.  
  720.  This should only be done for one level, so the update container takes the
  721.  free list of the target container. Any free list that is in container that
  722.  is further down may be used already and should not be used.
  723. */
  724.  
  725. void cmTakeOverFreeList(ContainerPtr toContainer, ContainerPtr container)
  726. {
  727.     TOCValuePtr         theValue;
  728.     
  729.     TOCValueHdrPtr freeSpaceValueHdr = container->freeSpaceValueHdr;
  730.     if (freeSpaceValueHdr) {
  731.         theValue = (TOCValuePtr)cmGetListHead(&freeSpaceValueHdr->valueList);
  732.         while (theValue) {
  733.             addToPermFreeList(toContainer,
  734.                                                 theValue->value.notImm.value, theValue->value.notImm.valueLen);
  735.             theValue = (TOCValuePtr)cmGetNextListCell(theValue);
  736.         } /* value */
  737.     }
  738. }
  739.  
  740. /*--------------------------------------------------------------------------*
  741.  | cmWriteData - write data to container with possible resuse of free space |
  742.  *--------------------------------------------------------------------------*
  743.  
  744.  This routine is the Container Manager's low-level value data writer.  It takes a value
  745.  header, and size bytes in the buffer and writes it to the container via the output
  746.  handler.  The amount written is returned.  If it is not equal to the passed size, the
  747.  caller should report an error.
  748.  
  749.  The reason this routine is used rather than using the CMfwrite() handler call directly is
  750.  that this routine checks to see if the container has been opened to reuse free space.  If
  751.  it hasn't, we degenerate into a simple CMfwrite() call.  If it has, then we use the free
  752.  list, built by cmAddToFreeList(), to write out the data segments to reuse the free space.
  753.  
  754.  In all cases the data written is recorded as value segments in the value list belonging
  755.  to the specified value header. The new segments are appended on to the END of the segment
  756.  list.  It is up to the caller to guarantee this is where the segments are to go.  The
  757.  continued flags are appropriately set.
  758.  
  759.  Note, as just mentioned, use this routine ONLY for appending data segments to a value.
  760.  Also, use this routine ONLY if continued segments are permitted for the data.  This means
  761.  you cannot call this routine to write global names.  They are always written as single
  762.  segments.
  763.  
  764.  Even with these restrictions, for the main case, i.e., CMWriteValueData(), this is not a
  765.  problem.  CMWriteValueData() is the primary caller.  It knows what it's doing with the
  766.  data (lets hope so).  So it knows when to call us here.
  767.  
  768.  The net effect is to reuse free space whenever we can if the container was opened for
  769.  updating, and to do straight CMfwrite() otherwise.
  770. */
  771.  
  772. CM_ULONG cmWriteData(TOCValueHdrPtr theValueHdr, CM_UCHAR *buffer,
  773.                                          CM_ULONG size)
  774. {
  775.     ContainerPtr  container = theValueHdr->container->updatingContainer;
  776.     TOCValuePtr        prevValue;
  777.     CM_ULONG             chunkSize, offset, amountWritten = 0;
  778.     TOCValueBytes valueBytes;
  779.     Boolean                appendToPrev;
  780.  
  781.     /* Write out all the data (size bytes of it).  To save a little code space we check     */
  782.     /* for updating in the loop.  If we are not updating we will attempt to do a standard    */
  783.     /* CMfwrite() of all the data as a single value segment.  That is also what happens        */
  784.     /* when we run out of free space.  Then we try to write out all the remaining data        */
  785.     /* as a single segment.  The code is the same, so that's why the update check is in     */
  786.     /* the loop.  If we are updating, and we do have free list entries, we use them to        */
  787.     /* see where to write and how much.  This will reuse the free list space.                            */
  788.     
  789.     prevValue = (TOCValuePtr)cmGetListTail(&theValueHdr->valueList); /* last value seg        */
  790.     
  791.     while (size > 0) {                                                                    /* loop till no more data                    */
  792.         if ((container->useFlags & kCMReuseFreeSpace)==0)    /* if not reusing free space...        */
  793.             chunkSize = 0;                                                                    /* ...this will cause std write        */
  794.         else                                                                                            /* if updating,get some free space*/
  795.             offset = cmGetFreeListEntry(container, size, false, &chunkSize);
  796.         
  797.         if (chunkSize == 0) {                                                            /* if no free space to reuse...        */
  798.             offset = CMgetContainerSize(container);
  799.             CMfseek(container, 0, kCMSeekEnd);                            /* position to current eof                */
  800.             if (CMfwrite(container, buffer, sizeof(CM_UCHAR), size) == size) {             /* write    */
  801.                 amountWritten += size;                                                /* count total amount written            */
  802.                 container->physicalEOF = offset + size;                /* update next free container byte*/
  803.                 SetLogicalEOF(container->physicalEOF);                /* logical EOF == physical EOF        */
  804.                 (void)cmSetValueBytes(container, &valueBytes, Value_NotImm, offset, size);
  805.                 cmAppendValue(theValueHdr, &valueBytes, 0);        /* append new value segment                */
  806. #if CMKEEP_CONTINUE_FLAG
  807.                 if (prevValue != NULL) {                                            /* if this is not 1st segment...    */
  808.                     prevValue->flags |= kCMContinued;                        /* ...flag last seg as cont'd            */
  809.                     theValueHdr->valueFlags |= ValueContinued;    /* ...also echo flag in the hdr        */
  810.                 }
  811. #endif
  812.             }
  813.             return (amountWritten);                                                    /* return amount we wrote                    */
  814.         } /* chunkSize == 0 */
  815.         
  816.         /* If we get here then we are going to reuse a free space segment...                                */
  817.         
  818.         CMfseek(container, offset, kCMSeekSet);                        /* overwrite the free space chunk    */
  819.         if (CMfwrite(container, buffer, sizeof(CM_UCHAR), chunkSize) != chunkSize) 
  820.             return (amountWritten);
  821.         
  822.         /* if the free space is right after a previous free space segment, just extend that */
  823.  
  824.         appendToPrev = true;
  825.         if (prevValue != NULL) {                                                    /* if this is not 1st segment...    */
  826.             if (((prevValue->flags & kCMImmediate) == 0) &&
  827.                     ((prevValue->value.notImm.value+prevValue->value.notImm.valueLen) == offset)) {
  828.                 prevValue->value.notImm.valueLen += chunkSize;    /* just add to previous value */
  829.                 theValueHdr->size += chunkSize;                                
  830.                 appendToPrev = false;
  831. #if CMKEEP_CONTINUE_FLAG
  832.             } else {                                                                                /* it is discontinous                            */
  833.                 prevValue->flags |= kCMContinued;                            /* ...flag last seg as cont'd            */
  834.                 theValueHdr->valueFlags |= ValueContinued;        /* ...also echo flag in the hdr        */
  835. #endif
  836.             };
  837.         }
  838.         
  839.         if (appendToPrev) {
  840.             (void)cmSetValueBytes(container, &valueBytes, Value_NotImm, offset, chunkSize);
  841.             prevValue = cmAppendValue(theValueHdr, &valueBytes, 0);    /* append new value segment    */
  842.             if (prevValue == NULL) return (amountWritten);
  843.         }
  844.         
  845.         offset += chunkSize;                                                            /* set logical EOF                                */
  846.         SetLogicalEOF(offset);
  847.         
  848.         buffer                 += chunkSize;                                                /* point to next chunk to write        */
  849.         amountWritten += chunkSize;                                                /* count total amount written            */
  850.         size                     -= chunkSize;                                                /* reduce amount yet to be written*/
  851.     } /* while */                                                                                /* loop through all the data            */
  852.     
  853.     return (amountWritten);                                                            /* return amount we wrote                    */
  854. }
  855.  
  856.  
  857. /*----------------------------------------------------------------*
  858.  | cmDeleteFreeSpace - delete free space beyond a specified point |
  859.  *----------------------------------------------------------------*
  860.  
  861.  This routine is called to remove all free list entries that have their space beyond the
  862.  specified offset, beyondHere.  All entries with starting offsets greater than or equal
  863.  to beyondHere are removed.  If one spans beyondHere it will be reduced appropriately.
  864.  
  865.  These entries are removed so so that we may overwrite from beyondHere with a new TOC.
  866.  Since we are reusing that space for the TOC we obviously can't keep free list entries for
  867.  it.
  868. */
  869.  
  870. void cmDeleteFreeSpace(ContainerPtr container, CM_ULONG beyondHere)
  871. {
  872.     TOCValuePtr        theValue, nextValue;
  873.     CM_ULONG             offset, size, newLen;
  874.     TOCValuePtr        spaceDeletedValue = container->spaceDeletedValue;
  875.  
  876.     if (container->freeSpaceValueHdr == NULL) return;                /* exit if no free list                */
  877.     
  878.     theValue = (TOCValuePtr)cmGetListHead(&container->freeSpaceValueHdr->valueList);
  879.     
  880.     while (theValue) {                                                                            /* ...scan free list                    */
  881.         nextValue = (TOCValuePtr)cmGetNextListCell(theValue);    /* get next now for deletes        */
  882.         offset    = theValue->value.notImm.value;                            /* offset of a free chunk            */
  883.         size    = theValue->value.notImm.valueLen;                        /* size of a free chunk                */
  884.         
  885.         if (offset >= beyondHere) {                                                        /* if chunk entirely beyond        */
  886.             spaceDeletedValue->value.imm.ulongValue -= size;
  887.             deleteFreeListEntry(theValue);                                            /* ...delete it                                */
  888.         }
  889.         else if (offset + size > beyondHere) {                                 /* if partial...                            */
  890.             newLen = beyondHere - offset;                                                /* ...cut size down                        */
  891.             size -= newLen;                                                                            /* actual size deleted                */
  892.             spaceDeletedValue->value.imm.ulongValue -= size;        /* decr space deleted                    */
  893.             #if TOC1_SUPPORT
  894.             if (container->majorVersion == 1) {                                    /* and if format 1 TOC...            */
  895.                 if (newLen <= TOCentrySize)                                             /* ...and too small to keep        */
  896.                     deleteFreeListEntry(theValue);                                    /* ...delete it too                        */
  897.                 else {                                                                                        /* ...if still acceptable            */
  898.                     container->freeSpaceValueHdr->size -= size;
  899.                     theValue->value.notImm.valueLen = newLen;                /* ...set its new smaller size*/
  900.                 }
  901.             } else {                                                                                        /* if >format 1 TOC                        */
  902.                 if (newLen <= MinTOCSize)                                                 /* ...and still too small            */
  903.                     deleteFreeListEntry(theValue);                                    /* ...delete it too                        */
  904.                 else {                                                                                        /* ...if still acceptable            */
  905.                     container->freeSpaceValueHdr->size -= size;
  906.                     theValue->value.notImm.valueLen = newLen;                /* ...set its new smaller size*/
  907.                 }
  908.             }
  909.             #else
  910.             if (newLen <= MinTOCSize)                                                     /* ...but if too small to keep*/
  911.                 deleteFreeListEntry(theValue);                                        /* ...delete it too                        */
  912.             else {                                                                                            /* ...if still acceptable            */
  913.                 container->freeSpaceValueHdr->size -= size;
  914.                 theValue->value.notImm.valueLen = newLen;                    /* ...set its new smaller size*/
  915.             }
  916.             #endif
  917.         }
  918.         
  919.         theValue = nextValue;                                                                    /* loop till no more entries    */
  920.     } /* while */
  921. }
  922.  
  923.                                                           CM_END_CFUNCTIONS
  924.